/** First and Higher Order Statistics: $(LUCKY Histograms) and $(LUCKY N-grams).

    Copyright: Per Nordlöw 2018-.
    License: $(WEB boost.org/LICENSE_1_0.txt, Boost License 1.0).
    Authors: $(WEB Per Nordlöw)

    TODO: Replace static ifs with static final switch when Issue 6921 is fixed

    TODO: Remove overloads using std.string:representation and use sparse maps
    over dchar for strings.
*/
module nxt.ngram;

import nxt.static_bitarray;
import std.range: InputRange, ElementType, isInputRange;
import std.traits: isSomeChar, isUnsigned, isIntegral, isFloatingPoint, Unqual, isStaticArray, isIterable, isAssociativeArray, CommonType;
import std.stdint: uint64_t;
import std.typecons: Tuple, tuple;
import nxt.predicates: allZero, allEqualTo;
import nxt.nesses: denseness;
import nxt.rational: Rational;
// import msgpack;
import std.numeric: dotProduct;
import std.string: representation;
import std.conv: to;

// version = print;

/** N-Gram Model Kind. */
enum Kind
{
    saturated, // Standard Saturated Integers. Saturation is more robust than default integer wrap-around.
    binary // Binary Gram.
}

/** N-Gram Model Storage. */
enum Storage
{
    denseDynamic,// Dynamically allocated dense storage.
    denseStatic, // Statically allocated dense storage.
    sparse, // N-Dimensional/Level D Maps/Dictionaries.
}

/** N-Gram Model Symmetry. */
enum Symmetry
{
    ordered, // Order between elements matters.
    unordered, // Order of elements is ignored (relaxed). Tuples are sorted before inserted.
}

/**
   Computes $(LUCKY N-Gram) Model of Input Range $(D range).

   If N == 1 this N-gram becomes a standard $(LUCKY Histogram), also called a
   $(LUCKY Unigram).

   If Bin/Bucket Type $(D RequestedBinType), requested by user, is $(D void) it
   will be chosen automatically based on element type of $(D Range).

   TODO: Add optimized put() be precalculating maximum number of elements that
   can be inserted without any risk overflow.
*/
struct NGram(ValueType,
             int N = 1,
             Kind kind = Kind.saturated,
             Storage storage = Storage.denseDynamic,
             Symmetry symmetry = Symmetry.ordered,
             RequestedBinType = void,
             Range) if (is(RequestedBinType == void) ||
                        isUnsigned!RequestedBinType ||
                        isFloatingPoint!RequestedBinType)
{
    this(in Range range) @safe pure nothrow { put(range); }

    auto ref value() @property @safe pure inout nothrow { return _bins; }

    alias Q = Rational!ulong;

    @property static int order() @safe pure nothrow { return N; }

    enum isBinary = (kind == Kind.binary);
    enum isDense = (storage == Storage.denseStatic ||
                    storage == Storage.denseDynamic);
    enum isSparse = !isDense;
    enum cacheDeepDenseness = false;

    enum getStorage = storage;

    /** Returns: Documentation of the type of $(D this). */
    string typeName() @property const
    {
        string prefix;
        static      if (N == 1) { prefix = "Uni"; }
        else static if (N == 2) { prefix = "Bi"; }
        else static if (N == 3) { prefix = "Tri"; }
        else static if (N == 4) { prefix = "Qua"; }
        else static if (N == 5) { prefix = "Pen"; }
            else                    { prefix = to!string(N) ~ "-"; }
        string rval;
        static if (isBinary)
        {
            rval ~= "Bit";
        }
        else
        {
            rval ~= BinType.stringof;
        }
        rval ~= "-" ~ prefix ~ "Gram over " ~ ValueType.stringof ~ "s";
        return rval;
    }

    string toString() @property const
    {
        string rval = typeName ~ ": ";

        // print contents
        static if (isAA)
        {
            rval ~= to!string(_bins);
        }
        else if (N >= 2 ||
                 this.denseness < Q(1, 2)) // if less than half of the bins are occupied
        {
            // show as sparse
            rval ~= "[";

            // TODO: Replace these with recursion?
            static if (N == 1)
            {
                bool begun = false;
                foreach (ix, elt; _bins) // TODO: Make static_bitarray support ref foreach and make elt const ref
                {
                    if (elt)
                    {
                        if (begun) { rval ~= ", "; }
                        rval ~= "{" ~ to!string(ix) ~ "}#" ~ to!string(elt);
                        begun = true;
                    }
                }
            }
            else static if (N == 2)
            {
                bool begun = false;
                foreach (ix0, const ref elt0; _bins)
                {
                    foreach (ix1, elt1; elt0) // TODO: Make static_bitarray support ref foreach and make elt1 const ref
                    {
                        if (elt1)
                        {
                            if (begun) { rval ~= ", "; }
                            rval ~= ("{" ~
                                     to!string(ix0) ~ "," ~
                                     to!string(ix1) ~ "}#" ~
                                     to!string(elt1));
                            begun = true;
                        }
                    }
                }
            }
            else static if (N == 3)
            {
                bool begun = false;
                foreach (ix0, const ref elt0; _bins)
                {
                    foreach (ix1, const ref elt1; elt0)
                    {
                        foreach (ix2, elt2; elt1) { // TODO: Make static_bitarray support ref foreach and make elt2 const ref
                            if (elt2)
                            {
                                if (begun) { rval ~= ", "; }
                                rval ~= ("{" ~
                                         to!string(ix0) ~ "," ~
                                         to!string(ix1) ~ "," ~
                                         to!string(ix2) ~ "}#" ~
                                         to!string(elt2));
                                begun = true;
                            }
                        }
                    }
                }
            }
            else static if (N == 4)
            {
                bool begun = false;
                foreach (ix0, const ref elt0; _bins)
                {
                    foreach (ix1, const ref elt1; elt0)
                    {
                        foreach (ix2, elt2; elt1)
                        {
                            foreach (ix3, elt3; elt2) // TODO: Make static_bitarray support ref foreach and make elt2 const ref
                            {
                                if (elt3)
                                {
                                    if (begun) { rval ~= ", "; }
                                    rval ~= ("{" ~
                                             to!string(ix0) ~ "," ~
                                             to!string(ix1) ~ "," ~
                                             to!string(ix2) ~ "," ~
                                             to!string(ix3) ~ "}#" ~
                                             to!string(elt3));
                                    begun = true;
                                }
                            }
                        }
                    }
                }
            }
            else static if (N == 5)
            {
                bool begun = false;
                foreach (ix0, const ref elt0; _bins)
                {
                    foreach (ix1, const ref elt1; elt0)
                    {
                        foreach (ix2, const ref elt2; elt1)
                        {
                            foreach (ix3, const ref elt3; elt2) // TODO: Make static_bitarray support ref foreach and make elt2 const ref
                            {
                                foreach (ix4, elt4; elt3) // TODO: Make static_bitarray support ref foreach and make elt2 const ref
                                {
                                    if (elt4)
                                    {
                                        if (begun) { rval ~= ", "; }
                                        rval ~= ("{" ~
                                                 to!string(ix0) ~ "," ~
                                                 to!string(ix1) ~ "," ~
                                                 to!string(ix2) ~ "," ~
                                                 to!string(ix3) ~ "," ~
                                                 to!string(ix4) ~ "}#" ~
                                                 to!string(elt4));
                                        begun = true;
                                    }
                                }
                            }
                        }
                    }
                }
            }
            else
            {
                static assert(0, "N >= 5 not supported");
            }
            rval ~= "]";
        }
        else
        {
            rval ~= to!string(_bins); // default
        }

        static if (N == 1)
        {
            rval ~= " denseness:" ~ to!string(denseness);
        }
        else
        {
            rval ~= (" shallowDenseness:" ~ to!string(denseness(0)) ~
                     " deepDenseness:" ~ to!string(denseness(-1)));
        }

        return rval;
    }

    void reset() @safe nothrow
    {
        import nxt.algorithm_ex: reset;
        _bins.reset();
    }
    // alias reset = clear;

    bool empty() const pure @property @trusted nothrow
    {
        static if (isAA)
        {
            return _bins.length == 0;
        }
        else
        {
            return _bins.allZero;
        }
    }

    static if (N >= 2 &&
               storage != Storage.sparse)
    {
        Q shallowDenseness() const pure @property @trusted nothrow
        {
            static if (N == 2)
            {
                ulong x = 0;
                foreach (const ref elt0; 0..combE) // every possible first ngram element
                {
                    bool used = false;
                    foreach (elt1; 0..combE) // every possible second ngram element
                    {
                        if (_bins[elt0][elt1]) // if any bit is used
                        {
                            used = true; // we flag it and exit
                            break;
                        }
                    }
                    if (used) ++x;
                }
                return Q(x, combE);
            }
            else
            {
                return Q(1, 1);
            }
        }
    }

    typeof(this) opAssign(RhsRange)(in NGram!(ValueType, N, kind, storage, symmetry, RequestedBinType, RhsRange) rhs)
    if (isInputRange!RhsRange) // if (is(Unqual!Range == Unqual!RhsRange))
    {
        static if      (storage == Storage.denseDynamic)
            _bins = rhs._bins.dup;
        else static if (storage == Storage.sparse)
            _bins = cast(BinType[ValueType[N]])(rhs._bins.dup); // TODO: How can we prevent this cast?
        else static if (storage == Storage.denseStatic)
            _bins = rhs._bins;
        else
            static assert(0, "Cannot handle storage of type " ~ to!string(storage));
        return this;
    }

    static if (N == 1)
    {
        void normalize() @safe pure /* nothrow */
        {
            static if (kind != Kind.binary)
            {
                static if (isFloatingPoint!ValueType)
                {
                    immutable scaleFactor = (cast(real)1) / _bins.length; // precalc scaling
                }
                foreach (ref elt; _bins) // TODO: Why can this throw for associative arrays?
                {
                    static if (isIntegral!ValueType ||
                               isSomeChar!ValueType)
                    {
                        elt /= 2; // drop least significant bit
                    }
                    else static if (isFloatingPoint!ValueType)
                    {
                        elt =* scaleFactor;
                    }
                }
            }
        }
    }

    /** Invalidate Local Statistics. */
    void invalidateStats() @safe nothrow
    {
        static if (isAA && cacheDeepDenseness) { _deepDenseness = 0; }
    }

    /** Saturated Increment $(D x) by one. */
    ref T incs(T)(ref T x) @safe nothrow if (isIntegral!T) { if (x != T.max) { ++x; invalidateStats(); } return x; }
    /** Saturated Increment $(D x) by one. */
    ref T incs(T)(ref T x) @safe nothrow if (isFloatingPoint!T) { invalidateStats(); return ++x; }

    static if (kind == Kind.saturated)
    {
        /** Increase bin of $(D ng).
            Bin of ng must already be allocated if its stored in a map.
        */
        ref NGram inc(ValueType[N] ng) @safe pure nothrow
        {
            static if (isAA)
            {
                incs(_bins[ng]); // just one case!
            }
            else
            {
                static        if (N == 1)
                {
                    static if (storage == Storage.denseDynamic)
                    {
                        if (!_bins) { _bins = new BinType[noABins]; }
                    }
                    incs(_bins[ng[0]]);
                }
                else static if (N == 2)
                {
                    static if (storage == Storage.denseDynamic)
                    {
                        if (!_bins) { _bins = new BinType[][noABins]; }
                        if (!_bins[ng[0]]) { _bins[ng[0]] = new BinType[noABins]; }
                    }
                    incs(_bins[ng[0]][ng[1]]);
                }
                else static if (N == 3)
                {
                    static if (storage == Storage.denseDynamic)
                    {
                        if (!_bins) { _bins = new BinType[][][noABins]; }
                        if (!_bins[ng[0]]) { _bins[ng[0]] = new BinType[][noABins]; }
                        if (!_bins[ng[0]][ng[1]]) { _bins[ng[0]][ng[1]] = new BinType[noABins]; }
                    }
                    incs(_bins[ng[0]][ng[1]][ng[2]]);
                }
                else static if (N == 4)
                {
                    static if (storage == Storage.denseDynamic)
                    {
                        if (!_bins) { _bins = new BinType[][][][noABins]; }
                        if (!_bins[ng[0]]) { _bins[ng[0]] = new BinType[][][noABins]; }
                        if (!_bins[ng[0]][ng[1]]) { _bins[ng[0]][ng[1]] = new BinType[][noABins]; }
                        if (!_bins[ng[0]][ng[1]][ng[2]]) { _bins[ng[0]][ng[1]][ng[2]] = new BinType[noABins]; }
                    }
                    incs(_bins[ng[0]][ng[1]][ng[2]][ng[3]]);
                }
                else static if (N == 5)
                {
                    static if (storage == Storage.denseDynamic)
                    {
                        if (!_bins) { _bins = new BinType[][][][][noABins]; }
                        if (!_bins[ng[0]]) { _bins[ng[0]] = new BinType[][][][noABins]; }
                        if (!_bins[ng[0]][ng[1]]) { _bins[ng[0]][ng[1]] = new BinType[][][noABins]; }
                        if (!_bins[ng[0]][ng[1]][ng[2]]) { _bins[ng[0]][ng[1]][ng[2]] = new BinType[][noABins]; }
                        if (!_bins[ng[0]][ng[1]][ng[2]][ng[3]]) { _bins[ng[0]][ng[1]][ng[2]][ng[3]] = new BinType[noABins]; }
                    }
                    incs(_bins[ng[0]][ng[1]][ng[2]][ng[3]][ng[4]]);
                }
                else
                {
                    static assert(0, "N >= 6 not supported");
                }
            }
            return this;
        }
    }

    /** Returns: Bin Count of NGram $(D ng). */
    BinType opIndex(T)(in T ng) const @safe pure nothrow if (isIntegral!T ||
                                                             isStaticArray!T)
    {
        static if (isAA)
        {
            if (ng in _bins)
            {
                return _bins[ng];
            }
            else
            {
                return 0; // empty means zero bin
            }
        }
        else
        {
            static      if (N == 1) { return _bins[ng]; }
            else static if (N == 2) { return _bins[ng[0]][ng[1]]; }
            else static if (N == 3) { return _bins[ng[0]][ng[1]][ng[2]]; }
            else static if (N == 4) { return _bins[ng[0]][ng[1]][ng[2]][ng[3]]; }
            else static if (N == 5) { return _bins[ng[0]][ng[1]][ng[2]][ng[3]][ng[4]]; }
            else { static assert(0, "N >= 6 not supported"); }
        }
    }

    /* ref BinType opIndexAssign(Index)(BinType b, Index i) @trusted pure nothrow if (isIntegral!Index) in { */

    /* } */

    /** Returns: Bin Count of NGram $(D ng). */
    auto opIndexAssign(T)(in T ng) const @safe pure nothrow if (isIntegral!T ||
                                                                isStaticArray!T)
    {
        static if (isAA)
        {
            if (ng in _bins)
            {
                return _bins[ng];
            }
            else
            {
                return 0; // empty means zero bin
            }
        }
        else
        {
            static      if (N == 1) { return _bins[ng]; }
            else static if (N == 2) { return _bins[ng[0]][ng[1]]; }
            else static if (N == 3) { return _bins[ng[0]][ng[1]][ng[2]]; }
            else static if (N == 4) { return _bins[ng[0]][ng[1]][ng[2]][ng[3]]; }
            else static if (N == 5) { return _bins[ng[0]][ng[1]][ng[2]][ng[3]][ng[4]]; }
            else { static assert(0, "N >= 6 not supported"); }
        }
    }

    /** Put NGram Element $(D ng) in $(D this).
     */
    ref NGram put(ValueType[N] ng) @safe pure nothrow
    {
        static if (isBinary)
        {
            static      if (N == 1) { _bins[ng[0]] = true; }
            else static if (N == 2) { _bins[ng[0]][ng[1]] = true; }
            else static if (N == 3) { _bins[ng[0]][ng[1]][ng[2]] = true; }
            else static if (N == 4) { _bins[ng[0]][ng[1]][ng[2]][ng[3]] = true; }
            else static if (N == 5) { _bins[ng[0]][ng[1]][ng[2]][ng[3]][ng[4]] = true; }
            else { static assert(0, "N >= 6 not supported"); }
        }
        else
        {
            static if (isAA)
            {
                if (ng in _bins)
                {
                    inc(ng); // increase bin
                }
                else
                {
                    _bins[ng] = 1; // initial bin count
                }
            }
            else
            {
                inc(ng);
            }
        }
        invalidateStats();
        return this;
    }

    /** Put NGram Elements $(D range) in $(D this).
     */
    ref NGram put(T)(in T range) @safe pure nothrow if (isIterable!T)
    {
        static if (N == 1)
        {
            foreach (ix, const ref elt; range)
            {
                put([elt]);
            }
        }
        else static if (N == 2)
        {
            ValueType prev; // previous element
            foreach (ix, const ref elt; range)
            {
                if (ix >= N-1) { put([prev, elt]); }
                prev = elt;
            }
        }
        else static if (N == 3)
        {
            ValueType pprev, prev; // previous elements
            foreach (ix, const ref elt; range)
            {
                if (ix >= N-1) { put([pprev, prev, elt]); }
                pprev = prev;
                prev = elt;
            }
        }
        else static if (N == 4)
        {
            ValueType ppprev, pprev, prev; // previous elements
            foreach (ix, const ref elt; range)
            {
                if (ix >= N-1) { put([ppprev, pprev, prev, elt]); }
                ppprev = pprev;
                pprev = prev;
                prev = elt;
            }
        }
        else static if (N == 5)
        {
            ValueType pppprev, ppprev, pprev, prev; // previous elements
            foreach (ix, const ref elt; range)
            {
                if (ix >= N-1) { put([pppprev, ppprev, pprev, prev, elt]); }
                pppprev = ppprev;
                ppprev = pprev;
                pprev = prev;
                prev = elt;
            }
        }
        return this;
    }

    /** Scalar (Dot) Product Match $(D this) with $(D rhs). */
    CommonType!(ulong, BinType) matchDenser(rhsValueType,
                                            Kind rhsKind = Kind.saturated,
                                            Storage rhsStorage = Storage.denseDynamic,
                                            RhsRange)(in NGram!(rhsValueType,
                                                                N,
                                                                rhsKind,
                                                                rhsStorage,
                                                                symmetry,
                                                                RequestedBinType,
                                                                RhsRange) rhs) const @trusted pure /* nothrow */
    {
        static if (this.isDense && rhs.isDense)
        {
            static if (N == 1) return dotProduct(this._bins, rhs._bins);
            else static assert(0, "N >= " ~ to!string(N) ~ " not supported");
        }
        else static if (this.isSparse)
        {
            typeof(return) sum = 0;
            foreach (ix, const ref bin; _bins) // assume lhs is sparsest
            {
                sum += bin*rhs[ix];
            }
            return sum;
        }
        else static if (rhs.isSparse)
        {
            typeof(return) sum = 0;
            foreach (ix, const ref bin; rhs._bins) // assume lhs is sparsest
            {
                sum += this[ix]*bin;
            }
            return sum;
        }
        else
        {
            static assert(0, "Combination of " ~ typeof(storage).stringof ~ " and " ~
                          typeof(rhsStorage).stringof ~ " not supported");
            return 0;
        }
    }

    auto opBinary(string op,
                  string file = __FILE__, int line = __LINE__)(in NGram rhs) const @trusted pure /* nothrow */
    {
        NGram tmp;
        static if (this.isSparse ||
                   rhs.isSparse)
        {
            void doIt(in NGram a, in NGram b) // more functional than orderInPlace
            {
                foreach (ix, const ref bin; a._bins)
                {
                    if (ix in b._bins)
                    {
                        mixin("tmp._bins[ix] = bin " ~ op ~ " b._bins[ix];"); // propagate pointwise operation
                    }
                }
            }
            if (this.length < rhs.length) { doIt(this, rhs); }
            else                          { doIt(rhs, this); }
        }
        else static if (this.isBinary &&
                        rhs.isBinary)
        {
            mixin("tmp._bins = _bins " ~ op ~ "rhs._bins;"); // bitsets cannot be sliced (yet)
        }
        else static if (this.isDense &&
                        rhs.isDense &&
                        N == 1)
        {
            assert(this.length == rhs.length);
            import std.range: zip;
            import std.algorithm: map;
            import std.array: array;
            tmp._bins = zip(this._bins[], rhs._bins[]).map!(a => mixin("a[0] " ~ op ~ "a[1]"))().array; // TODO: Use zipWith when Issue 8715 is fixed
            /* foreach (ix, let; this._bins) { // TODO: Reuse Phobos algorithm or range */
            /*     mixin("tmp[ix] = _bins[ix] " ~ op ~ "rhs._bins[ix];"); */
            /* } */
        }
        else
        {
            static assert(0, "Combination of " ~ to!string(this.getStorage) ~ " and " ~
                          to!string(rhs.getStorage) ~ " and N == " ~ to!string(N) ~ " not supported");
        }
        return tmp;
    }

    /** Determine Bin (Counter) Type. */
    static if (isBinary)
    {
        alias BinType = bool;
    }
    else static if (is(RequestedBinType == void))
    {
        alias BinType = uint64_t;   // Bin (counter) type. Count long by default.
    }
    else
    {
        alias BinType = RequestedBinType;
    }

    enum bitsE = 8 * ValueType.sizeof; /** Number of Bits in ValueType (element). TODO: This may have to be fixed for ref types. */
    enum combE = 2^^bitsE;  /** Number of combinations in element. */
    enum noABins = combE; // Number of bins per array dimension
    enum noBins = combE^^N; /** Maximum number of bins (possible). */

    // Determine storage structure base on element type.
    static if (storage == Storage.sparse)
    {
        BinType[ValueType[N]] _bins;
    }
    else static if (isBinary &&
                    N*bitsE <= 32) // safely fits on stack
    {
        static if        (storage == Storage.denseStatic)
        {
            static      if (N == 1) StaticBitArray!noABins _bins;
            else static if (N == 2) StaticBitArray!noABins[noABins] _bins;
            else static if (N == 3) StaticBitArray!noABins[noABins][noABins] _bins;
            else static assert(0, "Dense static N >= 4 does no safely fit on stack");
        }
        else static if (storage == Storage.denseDynamic)
        {
            static      if (N == 1) StaticBitArray!noABins _bins;
            else static if (N == 2) StaticBitArray!noABins[] _bins;
            else static if (N == 3) StaticBitArray!noABins[][] _bins;
            else static if (N == 4) StaticBitArray!noABins[][][] _bins;
            else static if (N == 5) StaticBitArray!noABins[][][][] _bins;
            else static assert(0, "N >= 6 not supported");
        }
        else static if (storage == Storage.sparse) // shouldn't happen
        {
        }
    }
    else static if (storage == Storage.denseStatic &&
                    (isUnsigned!ValueType ||
                     isSomeChar!ValueType) &&
                    N*bitsE <= 16) // safely fits on stack
    {
        static      if (N == 1) BinType[noABins] _bins;
        else static if (N == 2) BinType[noABins][noABins] _bins;
        else static assert(0, "Dense static N >= 3 does not safely fit on stack");
    }
    else static if (storage == Storage.denseDynamic &&
                    (isUnsigned!ValueType ||
                     isSomeChar!ValueType)) // safely fits on stack
    {
        static      if (N == 1) BinType[] _bins;
        else static if (N == 2) BinType[][] _bins;
        else static if (N == 3) BinType[][][] _bins;
        else static if (N == 4) BinType[][][][] _bins;
        else static if (N == 5) BinType[][][][][] _bins;
        else static assert(0, "N >= 6 not supported");
    }
    else
    {
        BinType[ValueType[N]] _bins;
    }

    private alias _bins this;

    enum isAA = isAssociativeArray!(typeof(_bins));

    static if (isAA && cacheDeepDenseness)
    {
        ulong _deepDenseness;    // Cache deep denseness in associative arrays
    }

    Q densenessUncached(int depth = -1) const pure @property @trusted nothrow
    {
        static if (isBinary)
        {
            static if (N >= 2)
            {
                if (N == 2 && depth == 0)  // if shallow wanted
                {
                    return shallowDenseness();
                }
            }
            return _bins.denseness;
        }
        else
        {
            static if (isAA)
            {
                return Q(_bins.length, noBins);
            }
            else
            {
                return _bins.denseness(depth);
            }
        }
    }

    /** Returns: Number of Non-Zero Elements in $(D range). */
    Q denseness(int depth = -1) const pure @property @safe nothrow
    {
        static if (isAA && cacheDeepDenseness)
        {
            if (depth == -1)  // -1 means deepDenseness
            {
                if (!_deepDenseness)  // if not yet defined.
                {
                    unqual(this).densenessUncached(depth).numerator; // calculate it
                }
                return Q(_deepDenseness, noBins);
            }
        }
        return densenessUncached(depth);
    }
}

/**
   Computes $(LUCKY Bi-Gram) of $(D range).
*/
auto ngram(int N = 2,
           Kind kind = Kind.saturated,
           Storage storage = Storage.denseDynamic,
           Symmetry symmetry = Symmetry.ordered,
           RequestedBinType = void,
           Range)(in Range range) @safe pure nothrow if (isIterable!Range)
{
    return NGram!(Unqual!(ElementType!Range), N,
                  kind, storage, symmetry, RequestedBinType, Unqual!(Range))(range);
}
auto sparseUIntNGramOverRepresentation(int N = 2,
                                       Kind kind = Kind.saturated,
                                       Symmetry symmetry = Symmetry.ordered)(in string range) @safe pure nothrow
{
    auto y = range.representation;
    return ngram!(N, kind, Storage.sparse, symmetry, uint)(y);
}

auto histogram(Kind kind = Kind.saturated,
               Storage storage = Storage.denseDynamic,
               Symmetry symmetry = Symmetry.ordered,
               RequestedBinType = void,
               Range)(in Range range) @safe pure nothrow if (isIterable!Range)
{
    return NGram!(Unqual!(ElementType!Range), 1, kind, storage, symmetry, RequestedBinType, Unqual!(Range))(range);
}
alias Hist = NGram;
alias hist = histogram;
alias unigram = histogram;

unittest
{
    const ubyte[] x = [1, 2, 3, 4, 5];
    const h = x.histogram!(Kind.saturated, Storage.denseStatic);
    const hh = h + h;

    auto h2 = x.histogram!(Kind.saturated, Storage.denseStatic);
    h2.put(x);
    assert(hh == h2);
}

unittest
{
    const ubyte[] x;
    const hDS = x.histogram!(Kind.saturated, Storage.denseStatic);  assert(hDS.empty);

    const hDD = x.histogram!(Kind.saturated, Storage.denseDynamic); assert(hDD.empty);

    auto h = x.histogram!(Kind.saturated, Storage.sparse); assert(h.empty);
    const ubyte[5] x1 = [1, 2, 3, 4, 5];
    h.put(x1); assert(!h.empty);
    assert(h.matchDenser(h) == x1.length);
    auto hh = h + h;
    assert(hh.matchDenser(hh) == 4*x1.length);

    h.destroy(); assert(h.empty);

    auto hU32 = x.histogram!(Kind.saturated, Storage.sparse, Symmetry.ordered, uint);
}

unittest
{
    alias ValueType = ubyte;
    const ValueType[3] x = [11, 12, 13];

    auto h = x.histogram!(Kind.saturated, Storage.denseStatic);
    assert(h[0] == 0);
    assert(h[11] == 1 && h[12] == 1 && h[13] == 1);
    assert(3 == h.matchDenser(h));

    h.put(x);
    assert(h[11] == 2 && h[12] == 2 && h[13] == 2);
    assert(12 == h.matchDenser(h));

    version(print) dbg(h);

    auto hD = x.histogram!(Kind.saturated, Storage.denseDynamic);
    version(print) dbg(hD);
}

unittest
{
    alias ValueType = ulong;
    const ValueType[3] x = [1, 2, 3];
    auto h = x.histogram!(Kind.saturated, Storage.denseStatic);
    h.put([4, 5, 6]);
    assert(h.length == 6);
}

/**
   Computes $(LUCKY Binary Histogram) of $(D range).
*/
auto bistogram(Range)(in Range range) @safe pure nothrow if (isIterable!Range)

{
    return NGram!(Unqual!(ElementType!Range), 1,
                  Kind.binary,
                  Storage.denseStatic,
                  Symmetry.ordered,
                  void,
                  Unqual!Range)(range);
}
alias bunigram = bistogram;

unittest
{
    const ubyte[] x;
    const b = x.bistogram;
    assert(b.empty);

    // test const unqualification
    NGram!(ubyte, 1, Kind.binary, Storage.denseStatic, Symmetry.ordered, void, const(ubyte)[]) cb;
    cb = b;
    assert(cb == b);

    // test immutable unqualification
    NGram!(ubyte, 1, Kind.binary, Storage.denseStatic, Symmetry.ordered, void, immutable(ubyte)[]) ib;
    ib = b;
    assert(ib == b);
}

unittest
{
    const ubyte[3] x = [1, 2, 3];
    const h_ = x.bistogram;
    assert(8*h_.sizeof == 2^^8);
    const h = h_;
    assert(h[1] && h[2] && h[3]);
    assert(!h[0]);
    assert(!h[4]);

    const h2_ = h_;
    assert((h2_ & h_) == h2_);
    assert((h2_ | h_) == h2_);
    assert((h2_.value & h_.value) == h2_.value);
    assert((h2_.value | h_.value) == h2_.value);
}
unittest
{
    const ushort[3] x = [1, 2, 3];
    const h_ = x.bistogram;
    assert(8*h_.sizeof == 2^^16);
    const h = h_;
    assert(h[1] && h[2] && h[3]);
    assert(!h[0]);
    assert(!h[4]);
}

/**
   Computes $(LUCKY Binary (Occurrence) NGram) of Bytes in Input String $(D x).
*/
auto bistogramOverRepresentation(in string x) pure nothrow

{
    return bistogram(x.representation);
}
unittest
{
    const x = "abcdef";
    auto h = x.bistogramOverRepresentation;
    size_t ix = 0;
    foreach (const bin; h)
    {
        if (ix >= cast(ubyte)'a' &&
            ix <= cast(ubyte)'f')
        {
            assert(bin);
        }
        else
        {
            assert(!bin);
        }
        ++ix;
    }
    version(print) dbg(h);
}

/**
   Computes $(LUCKY Bi-Gram) of $(D range).
*/
auto bigram(Kind kind = Kind.saturated,
            Storage storage = Storage.denseDynamic,
            Symmetry symmetry = Symmetry.ordered,
            RequestedBinType = void,
            Range)(in Range range) @safe pure nothrow if (isIterable!Range)
{
    return NGram!(Unqual!(ElementType!Range), 2,
                  kind, storage, symmetry, RequestedBinType, Unqual!(Range))(range);
}
auto sparseUIntBigram(Kind kind = Kind.saturated,
                      Symmetry symmetry = Symmetry.ordered,
                      Range)(in Range range) @safe pure nothrow if (isIterable!Range)
{
    return NGram!(Unqual!(ElementType!Range), 2,
                  kind, Storage.sparse, symmetry, uint, Unqual!(Range))(range);
}

unittest
{
    const ubyte[] x = [1, 2, 3, 3, 3, 4, 4, 5];

    auto bSp = x.bigram!(Kind.saturated, Storage.sparse);
    alias SparseNGram = Unqual!(typeof(bSp));

    // check msgpacking
    // auto bSPBytes = bSp.pack();
    // SparseNGram bSp_;
    // bSPBytes.unpack(bSp_);
    // assert(bSp == bSp_);

    auto bS = x.bigram!(Kind.saturated, Storage.denseStatic);
    const bSCopy = bS;
    bS.put(x);
    assert(bS != bSCopy);

    const bD = x.bigram!(Kind.saturated, Storage.denseDynamic);
    version(print) dbg(bD);

    const bb = x.bigram!(Kind.binary, Storage.denseStatic);
    version(print) dbg(typeof(bb._bins).stringof);

    assert(bb.denseness(0).numerator == 4);
    // assert(bb.denseness(-1).numerator == 6);
}
unittest
{
    const ubyte[] x = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11];

    const bS = x.bigram!(Kind.saturated, Storage.denseStatic);
    version(print) dbg(bS);
    assert(bS.denseness.numerator == x.length - bS.order + 1);

    const bB = x.bigram!(Kind.binary, Storage.denseStatic);
    version(print) dbg(bB);
}

unittest
{
    const x = [1, 2, 3, 4, 5];
    auto h = x.bigram!(Kind.saturated, Storage.sparse);
    assert(h.matchDenser(h) == x.length - 1);
}

/**
   Computes $(LUCKY Tri-Gram) of $(D range).
*/
auto trigram(Kind kind = Kind.saturated,
             Storage storage = Storage.denseDynamic,
             Symmetry symmetry = Symmetry.ordered,
             RequestedBinType = void,
             Range)(in Range range) @safe pure nothrow if (isIterable!Range)
{
    return NGram!(Unqual!(ElementType!Range), 3,
                  kind, storage, symmetry, RequestedBinType, Unqual!(Range))(range);
}
auto sparseUIntTrigram(Kind kind = Kind.saturated,
                      Symmetry symmetry = Symmetry.ordered,
                      Range)(in Range range) @safe pure nothrow if (isIterable!Range)
{
    return NGram!(Unqual!(ElementType!Range), 3,
                  kind, Storage.sparse, symmetry, uint, Unqual!(Range))(range);
}
unittest
{
    const ubyte[] x = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11];

    const bS = x.trigram!(Kind.saturated, Storage.denseStatic);
    version(print) dbg(bS);
    assert(bS.denseness.numerator == x.length - bS.order + 1);

    const bD = x.trigram!(Kind.saturated, Storage.denseDynamic);
    version(print) dbg(bD);

    const bB = x.trigram!(Kind.binary, Storage.denseStatic);
    /* version(print) dbg(bB); */
}

/**
   Computes $(LUCKY Qua-Gram) of $(D range).
*/
auto quagram(Kind kind = Kind.saturated,
             Storage storage = Storage.denseDynamic,
             Symmetry symmetry = Symmetry.ordered,
             RequestedBinType = void,
             Range)(in Range range) @safe pure nothrow if (isIterable!Range)
{
    return NGram!(Unqual!(ElementType!Range), 4,
                  kind, storage, symmetry, RequestedBinType, Unqual!(Range))(range);
}
auto sparseUIntQuagram(Kind kind = Kind.saturated,
                       Symmetry symmetry = Symmetry.ordered,
                       Range)(in Range range) @safe pure nothrow if (isIterable!Range)
{
    return NGram!(Unqual!(ElementType!Range), 4,
                  kind, Storage.sparse, symmetry, uint, Unqual!(Range))(range);
}
unittest
{
    const ubyte[] x = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11];

    const bD = x.quagram!(Kind.saturated, Storage.denseDynamic);
    version(print) dbg(bD);
    assert(bD.denseness.numerator == x.length - bD.order + 1);
}
auto sparseUIntQuagramOverRepresentation(in string x) pure nothrow
{
    return sparseUIntQuagram(x.representation);
}

/**
   Computes $(LUCKY Pen-Gram) of $(D range).
*/
auto pengram(Kind kind = Kind.saturated,
             Storage storage = Storage.denseDynamic,
             Symmetry symmetry = Symmetry.ordered,
             RequestedBinType = void,
             Range)(in Range range) @safe pure nothrow if (isIterable!Range)
{
    return NGram!(Unqual!(ElementType!Range), 5,
                  kind, storage, symmetry, RequestedBinType, Unqual!(Range))(range);
}
unittest
{
    const ubyte[] x = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11];

    const bS = x.pengram!(Kind.saturated, Storage.sparse);
    const bS_ = bS;
    assert(bS_ == bS);

    // skipping denseStatic because it doesn't fit stack anyway

    const bD = x.pengram!(Kind.saturated, Storage.denseDynamic);
    version(print) dbg(bD);
    assert(bD.denseness.numerator == x.length - bD.order + 1);
}
